{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Colors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortColors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #颜色分类"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个包含红色、白色和蓝色、共&nbsp;<code>n</code><em> </em>个元素的数组<meta charset=\"UTF-8\" />&nbsp;<code>nums</code>&nbsp;，<strong><a href=\"https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95\" target=\"_blank\">原地</a></strong>对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。</p>\n",
    "\n",
    "<p>我们使用整数 <code>0</code>、&nbsp;<code>1</code> 和 <code>2</code> 分别表示红色、白色和蓝色。</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p>必须在不使用库内置的 sort 函数的情况下解决这个问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,0,2,1,1,0]\n",
    "<strong>输出：</strong>[0,0,1,1,2,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,0,1]\n",
    "<strong>输出：</strong>[0,1,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 300</code></li>\n",
    "\t<li><code>nums[i]</code> 为 <code>0</code>、<code>1</code> 或 <code>2</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你能想出一个仅使用常数空间的一趟扫描算法吗？</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-colors](https://leetcode.cn/problems/sort-colors/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-colors](https://leetcode.cn/problems/sort-colors/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,0,2,1,1,0]', '[2,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return nums\n",
    "        \n",
    "        start = 0\n",
    "        end = len(nums) -1\n",
    "        \n",
    "        i = 0\n",
    "        while i <= end:\n",
    "            if nums[i] == 2:\n",
    "                nums[i], nums[end] = nums[end], nums[i]\n",
    "                end -= 1\n",
    "            elif nums[i] == 0:\n",
    "                nums[i], nums[start] = nums[start], nums[i]\n",
    "                start += 1\n",
    "                i += 1\n",
    "            else:    \n",
    "                i += 1\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        zero,two,i=-1,n,0\n",
    "        while i<two:\n",
    "            if nums[i]==0:\n",
    "                nums[zero+1],nums[i]=nums[i],nums[zero+1]\n",
    "                zero += 1\n",
    "                i += 1\n",
    "            elif nums[i]==2:\n",
    "                nums[i],nums[two-1]=nums[two-1],nums[i]\n",
    "                two -= 1\n",
    "            else: i+=1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: 'List[int]') -> 'None':\n",
    "        i, s, e = 0, 0, len(nums)-1\n",
    "        while i <= e:\n",
    "            while i <= e and nums[i] == 2:\n",
    "                nums[i], nums[e] = nums[e], nums[i]\n",
    "                e -= 1\n",
    "            while i >= s and nums[i] == 0:\n",
    "                nums[i], nums[s] = nums[s], nums[i]\n",
    "                s += 1\n",
    "            i += 1\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: 'List[int]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums_0 = 0\n",
    "        nums_1 = 0\n",
    "        nums_2 = 0\n",
    "        \n",
    "        for i in range(len(nums)):                        \n",
    "            if nums[i]==0:\n",
    "                print(nums_0)\n",
    "                a=nums.pop(i)\n",
    "                nums.insert(nums_0,a)\n",
    "                nums_0+=1\n",
    "            elif nums[i]==1:\n",
    "                a=nums.pop(i)\n",
    "                print(nums_0)\n",
    "                nums.insert(nums_0+nums_1,a)\n",
    "                nums_1+=1\n",
    "                        \n",
    "        #print(n)\n",
    "        return\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        # [red, white, blue]\n",
    "        count = [0] * 3\n",
    "        for color in nums:\n",
    "            count[color] += 1\n",
    "            \n",
    "        for i in range(len(nums)):\n",
    "            if i < count[0]:\n",
    "                nums[i] = 0\n",
    "            elif i < count[0] + count[1]:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        p,q=0,n-1\n",
    "        t=0\n",
    "        while t<=q:\n",
    "            print(p,q,t,nums)\n",
    "            if nums[t]==2:\n",
    "                nums[t],nums[q]=nums[q],nums[t]\n",
    "                q-=1\n",
    "            elif nums[t]==0:\n",
    "                nums[t],nums[p]=nums[p],nums[t]\n",
    "                if p==t:\n",
    "                    p+=1\n",
    "                    t+=1\n",
    "                else:p+=1\n",
    "                \n",
    "            else:\n",
    "                t+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums)==0:\n",
    "            return\n",
    "        self.quick(nums, 0, len(nums)-1)\n",
    "    def quick(self, nums, lo, hi):\n",
    "        if lo>=hi:#此处条件不能忘记\n",
    "            return\n",
    "        j=self.partition(nums, lo, hi)\n",
    "        self.quick(nums, lo, j-1)\n",
    "        self.quick(nums, j+1, hi)\n",
    "    def partition(self, nums, lo, hi):\n",
    "        v=nums[lo]\n",
    "        i=lo+1\n",
    "        j=hi\n",
    "        while True:\n",
    "            while nums[i]<=v:\n",
    "                i+=1\n",
    "                if i>=hi:\n",
    "                    break\n",
    "            while nums[j]>v:\n",
    "                j-=1\n",
    "                if j==lo:\n",
    "                    break   \n",
    "            \"\"\"\n",
    "            while i<hi and nums[i]<v:\n",
    "                i+=1\n",
    "            while j>lo and nums[j]>v:\n",
    "                j-=1\n",
    "            \"\"\"\n",
    "            if i>=j:#会有取等号是因为如果相等，没必要交换\n",
    "                break\n",
    "            nums[i], nums[j]=nums[j], nums[i]\n",
    "        nums[j],nums[lo] = nums[lo], nums[j]\n",
    "        return j\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        nums.sort()\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        zero,two,i = -1,len(nums),0\n",
    "        while i<two:\n",
    "            if nums[i]==0:\n",
    "                zero += 1\n",
    "                nums[i],nums[zero] = nums[zero],nums[i]\n",
    "                i+=1\n",
    "            elif nums[i]==2:\n",
    "                two -= 1\n",
    "                nums[i],nums[two] = nums[two],nums[i]\n",
    "            else:\n",
    "                i+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        one = 0\n",
    "        zero = 0\n",
    "        two = len(nums)-1\n",
    "        while one<=two:\n",
    "            if nums[one]==1:\n",
    "                one+=1\n",
    "            elif nums[one]==0:\n",
    "                nums[zero],nums[one]=nums[one],nums[zero]\n",
    "                zero+=1\n",
    "                one+=1\n",
    "            elif nums[one]==2:\n",
    "                nums[one],nums[two]=nums[two],nums[one]\n",
    "                two-=1\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        less,more = -1,len(nums)\n",
    "        cur = 0\n",
    "        while cur < more:\n",
    "            if nums[cur] == 0:\n",
    "                less += 1\n",
    "                nums[less],nums[cur] = nums[cur],nums[less]\n",
    "                cur += 1\n",
    "            elif nums[cur] == 1:\n",
    "                cur += 1\n",
    "            else:\n",
    "                more -= 1\n",
    "                nums[cur],nums[more] = nums[more],nums[cur]\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        x = nums.count(0)\n",
    "        y = nums.count(1)\n",
    "        z = nums.count(2)\n",
    "        res = [0 for i in range(x)] + [1 for i in range(y)] + [2 for i in range(z)]\n",
    "        for i in range(len(nums)):\n",
    "            if i < x:\n",
    "                nums[i] = 0\n",
    "            elif i < y+x:\n",
    "                nums[i] = 1\n",
    "            else:\n",
    "                nums[i] = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #三指针处理:\n",
    "        n = len(nums)\n",
    "        p0 = 0   #0元素左边界\n",
    "        p2 = n - 1\n",
    "        p1 = 0\n",
    "        while p1 <= p2:\n",
    "            if nums[p1] == 0:\n",
    "                nums[p0], nums[p1] = nums[p1], nums[p0]\n",
    "                p0 += 1\n",
    "                p1 += 1\n",
    "            elif nums[p1] == 2:\n",
    "                nums[p2], nums[p1] = nums[p1], nums[p2]\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #nums 之中只有 0 1 2 三种数\n",
    "        length = len(nums)\n",
    "        l = 0\n",
    "        r = length-1\n",
    "        i = 0\n",
    "        while i <= r:\n",
    "            if nums[i] == 0:\n",
    "                nums[l],nums[i] = nums[i],nums[l]\n",
    "                l += 1\n",
    "                i += 1\n",
    "            elif nums[i] == 2:\n",
    "                nums[i],nums[r] = nums[r],nums[i]\n",
    "                r -= 1\n",
    "            else:\n",
    "                i += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums_0 = 0\n",
    "        nums_1 = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0:\n",
    "                nums_0 += 1\n",
    "            elif nums[i] ==1:\n",
    "                nums_1 += 1\n",
    "        for i in range(nums_0):\n",
    "            nums[i] = 0\n",
    "        for i in range(nums_0, nums_0 + nums_1):\n",
    "            nums[i] = 1\n",
    "        for i in range(nums_0 + nums_1,len(nums)):\n",
    "            nums[i] = 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        j = len(nums) - 1\n",
    "        k = 0\n",
    "        while i <= j:\n",
    "            if nums[i] == 2:\n",
    "                nums[i],nums[j] = nums[j], nums[i]\n",
    "                j -= 1\n",
    "            elif nums[i] == 0:\n",
    "                nums[k], nums[i] = nums[i], nums[k]\n",
    "                k += 1\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return\n",
    "        numsSize=len(nums)\n",
    "        point0=0\n",
    "        point1=0\n",
    "        for i in range(numsSize):\n",
    "            if nums[i]==1:\n",
    "                nums[i],nums[point1]=nums[point1],nums[i]\n",
    "                point1+=1;\n",
    "            if nums[i]==0:\n",
    "                nums[i],nums[point0]=nums[point0],nums[i]\n",
    "                if point0<point1:\n",
    "                    nums[i],nums[point1]=nums[point1],nums[i]\n",
    "                point0+=1\n",
    "                point1+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        n = len(nums)\n",
    "        ptr = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i], nums[ptr] = nums[ptr], nums[i]\n",
    "                ptr += 1\n",
    "        for i in range(ptr, n):\n",
    "            if nums[i] == 1:\n",
    "                nums[i], nums[ptr] = nums[ptr], nums[i]\n",
    "                ptr += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        p0 = p1 = 0 \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                nums[i], nums[p1] = nums[p1], nums[i]\n",
    "                p1 += 1\n",
    "            elif nums[i] == 0:\n",
    "                nums[i], nums[p0] = nums[p0], nums[i]\n",
    "                if p0 < p1:  # p0 p1拉开差距之后p0后面的1会被换出去\n",
    "                    nums[i], nums[p1] = nums[p1], nums[i]\n",
    "                p0 += 1 \n",
    "                p1 += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        size = len(nums)\n",
    "        if(size == 0):\n",
    "            return 0\n",
    "        \n",
    "        l, r = 0, size-1\n",
    "        cur = 0\n",
    "        while(cur <= r):\n",
    "            if(l<=r and nums[cur] == 0):\n",
    "                # swap(nums[i], nums[l])\n",
    "                nums[l], nums[cur] = nums[cur], nums[l]\n",
    "                l += 1\n",
    "                cur += 1\n",
    "            elif(r>=0 and nums[cur] == 2):\n",
    "                nums[r], nums[cur] = nums[cur], nums[r]\n",
    "                r -= 1\n",
    "            else:\n",
    "                cur += 1\n",
    "            print(l, r)\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        '''\n",
    "        荷兰三色旗问题解\n",
    "        '''\n",
    "        # 对于所有 idx < p0 : nums[idx < p0] = 0\n",
    "        # curr是当前考虑元素的下标\n",
    "        p0 = curr = 0\n",
    "        # 对于所有 idx > p2 : nums[idx > p2] = 2\n",
    "        p2 = len(nums) - 1\n",
    "\n",
    "        while curr <= p2:\n",
    "            print (p0, curr, p2)\n",
    "            if nums[curr] == 0:\n",
    "                nums[p0], nums[curr] = nums[curr], nums[p0]\n",
    "                p0 += 1\n",
    "                curr += 1\n",
    "            elif nums[curr] == 2: # curr 不动，保证了不会 curr 跳过 2，因为交换后也可能是 2\n",
    "                nums[curr], nums[p2] = nums[p2], nums[curr]\n",
    "                p2 -= 1\n",
    "            else:\n",
    "                curr += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n != 0:\n",
    "            zero = 0\n",
    "            two = n - 1\n",
    "            index = 0\n",
    "            while index <= two and zero < n and two > 0:\n",
    "                print(index,two,zero)\n",
    "                if nums[index] == 0:\n",
    "                    nums[zero],nums[index] = nums[index],nums[zero]\n",
    "                    zero += 1\n",
    "                    index += 1\n",
    "\n",
    "                elif nums[index] == 2:\n",
    "                    nums[two],nums[index] = nums[index],nums[two]\n",
    "                    two -= 1\n",
    "\n",
    "                else:\n",
    "                    index += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        n = len(nums)\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                nums[i], nums[left] = nums[left], nums[i]\n",
    "                left += 1\n",
    "        for i in range(left, n):\n",
    "            if nums[i] == 1:\n",
    "                nums[i], nums[left] = nums[left], nums[i]\n",
    "                left += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i):\n",
    "                if nums[j] >= nums[j+1]:\n",
    "                    nums[j], nums[j+1] = nums[j+1], nums[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #笨的方法就是\n",
    "        #locatio：要插入的位置，\n",
    "        location = 0 \n",
    "        #依次遍历查询红色\n",
    "        for i in range(3):\n",
    "            #遍历红色，即nums[i]==i\n",
    "            for j in range(location,len(nums)):\n",
    "                if nums[j]==i:\n",
    "                    #交换位置\n",
    "                    nums[location],nums[j]=nums[j],nums[location]\n",
    "                    location +=1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(len(nums)-i-1):\n",
    "                if nums[j]>nums[j+1]:\n",
    "                    nums[j],nums[j+1]=nums[j+1],nums[j]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "考察排序方法：这里我选择快速排序。\n",
    "快速排序：\n",
    "    方法是element to position，人找位置。\n",
    "    为了方便，每次选择数组的第一个数作为pivot，然后通过交换，使得剩余数组的左边全部是比pivot小，或者相等的数，而右边全是比pivot大的数\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) == 1:\n",
    "            return\n",
    "        self.sort(nums, 0, len(nums) - 1)\n",
    "    \n",
    "    # 这里也是分治的思想。\n",
    "    def sort(self, nums, lo, hi):\n",
    "        if lo >= hi:\n",
    "            return\n",
    "        p = self.partition(nums, lo, hi)\n",
    "        self.sort(nums, 0, p - 1)\n",
    "        self.sort(nums, p + 1, hi)\n",
    "    \n",
    "    def partition(self, nums, lo, hi):\n",
    "        pivot = nums[lo]\n",
    "        i = lo + 1\n",
    "        j = hi\n",
    "        while i <= j:\n",
    "            while i < hi and nums[i] <= pivot:\n",
    "                i += 1\n",
    "            while j > lo and nums[j] > pivot:\n",
    "                j -= 1\n",
    "            if i >= j:\n",
    "                break\n",
    "            self.swap(nums, i, j)\n",
    "        # 此时的i > j的，所以lo只能和j换。\n",
    "        self.swap(nums, lo, j)\n",
    "        return j\n",
    "    \n",
    "    def swap(self, nums, i, j):\n",
    "        temp = nums[i]\n",
    "        nums[i] = nums[j]\n",
    "        nums[j] = temp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "from typing import List\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        self.__method12(nums)\n",
    "\n",
    "    \"\"\" \n",
    "        快速排序（不稳定）\n",
    "\n",
    "        时间复杂度：O(nlogn)\n",
    "        空间复杂度：O(logn)\n",
    "     \"\"\"\n",
    "    def __method1(self, nums: List[int]) -> None:\n",
    "        def quickSort(nums: List[int], left: int, right: int):\n",
    "            if left >= right:\n",
    "                return\n",
    "            low = left\n",
    "            high = right\n",
    "            target = nums[left]\n",
    "            while low < high:\n",
    "                while low < high and nums[high] > target:\n",
    "                    high -= 1\n",
    "                if low >= high:\n",
    "                    break\n",
    "                nums[low] = nums[high]\n",
    "                low += 1\n",
    "\n",
    "                while low < high and nums[low] < target:\n",
    "                    low += 1\n",
    "                if low >= high:\n",
    "                    break\n",
    "                nums[high] = nums[low]\n",
    "                high -= 1\n",
    "            nums[low] = target\n",
    "            quickSort(nums, left, low - 1)\n",
    "            quickSort(nums, low + 1, right)\n",
    "\n",
    "        quickSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    \"\"\" \n",
    "    三向切分快速排序\n",
    "\n",
    "    时间复杂度：O(nlogn)\n",
    "    空间复杂度：O(n)\n",
    "     \"\"\"\n",
    "    def __method12(self, nums: List[int]):\n",
    "        def quickSort(nums: List[int], left: int, right: int):\n",
    "            if left >= right:\n",
    "                return\n",
    "            # 在[left, right]范围内生成随机下标，该下标位置元素作为基准元素\n",
    "            r = random.randint(left, right)\n",
    "            \"\"\" \n",
    "            交换最右位置和random位置的元素，然后以最右位置元素为基准值\n",
    "            数组被分为三个区域，[左侧小于target区域 | 中间等于target区域 | 右侧大于target区域]\n",
    "            low表示左侧区域右边界、high表示右侧区域左边界，i表示中间未遍历元素的左边界（即中间区域右边界+1）\n",
    "            遍历元素，得到当前元素\n",
    "                当前元素 < target时，左侧区域将会新增一个元素；交换i和low+1位置元素，并让low，i同时右移；\n",
    "                当前元素 > target时，右侧区域将会新增一个元素；交换i和high-1位置元素，并让high左移，且i保持不变；\n",
    "                当前元素 = target时，中间区域将会新增一个元素；i右移；\n",
    "             \"\"\"\n",
    "            nums[r], nums[right] = nums[right], nums[r]\n",
    "            low = left - 1\n",
    "            high = right\n",
    "            i = low + 1\n",
    "            target = nums[right]\n",
    "            while i < high:\n",
    "                if nums[i] < target:\n",
    "                    nums[i], nums[low + 1] = nums[low + 1], nums[i]\n",
    "                    i += 1\n",
    "                    low += 1\n",
    "                elif nums[i] > target:\n",
    "                    nums[i], nums[high - 1] = nums[high - 1], nums[i]\n",
    "                    high -= 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            # 遍历结束后，最右侧元素应属于中间区域，因此交换最右与high位置元素，并让high右移（右侧区域变小一个）\n",
    "            nums[right], nums[high] = nums[high], nums[right]\n",
    "            high += 1\n",
    "            # 继续递归排序\n",
    "            quickSort(nums, left, low)\n",
    "            quickSort(nums, high, right)\n",
    "\n",
    "        quickSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    \"\"\" \n",
    "        归并排序（稳定）\n",
    "\n",
    "        时间复杂度：O(nlogn)\n",
    "        空间复杂度：O(n)\n",
    "     \"\"\"\n",
    "    def __method2(self, nums: List[int]):\n",
    "        \n",
    "        def mergeSort(nums: List[int], left: int, right: int):\n",
    "            if left >= right:\n",
    "                return\n",
    "            mid = left + math.floor((right - left) / 2)\n",
    "            mergeSort(nums, left, mid)\n",
    "            mergeSort(nums, mid + 1, right)\n",
    "            mergeList(nums, left, mid, right)\n",
    "        \n",
    "        def mergeList(nums: List[int], left: int, mid: int, right: int):\n",
    "            i = left\n",
    "            j = mid + 1\n",
    "            k = 0\n",
    "            temp = [None] * (right - left + 1)\n",
    "            while i <= mid and j <= right:\n",
    "                if nums[i] < nums[j]:\n",
    "                    temp[k] = nums[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    temp[k] = nums[j]\n",
    "                    j += 1\n",
    "                k += 1\n",
    "            while i <= mid:\n",
    "                temp[k] = nums[i]\n",
    "                k += 1\n",
    "                i += 1\n",
    "            while j <= right:\n",
    "                temp[k] = nums[j]\n",
    "                k += 1\n",
    "                j += 1\n",
    "            for i in range(0, k):\n",
    "                nums[left + i] = temp[i]\n",
    "\n",
    "        mergeSort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    \"\"\" \n",
    "        直接插入排序（稳定）\n",
    "\n",
    "        时间复杂度：O(n^2)\n",
    "        空间复杂度：O(1)\n",
    "     \"\"\"\n",
    "    def __method3(self, nums: List[int]):\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            j = i - 1\n",
    "            tmp = nums[i]\n",
    "            while j >= 0 and nums[j] > tmp:\n",
    "                nums[j + 1] = nums[j]\n",
    "                j -= 1\n",
    "            nums[j + 1] = tmp\n",
    "\n",
    "    \"\"\" \n",
    "        直接选择排序（不稳定）\n",
    "\n",
    "        时间复杂度：O(n^2)\n",
    "        空间复杂度：O(1)\n",
    "     \"\"\"\n",
    "    def __method4(self, nums: List[int]):\n",
    "        n = len(nums)\n",
    "        for i in range(0, n):\n",
    "            min = i\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] < nums[min]:\n",
    "                    min = j\n",
    "            tmp = nums[i]\n",
    "            nums[i] = nums[min]\n",
    "            nums[min] = tmp\n",
    "\n",
    "    \"\"\" \n",
    "        计数排序(改进版，稳定)\n",
    "\n",
    "        时间复杂度：O(n + k)，k = max - min + 1\n",
    "        空间复杂度：O(n + k)\n",
    "     \"\"\"\n",
    "    def __method5(self, nums: List[int]):\n",
    "        maxVal = max(nums)\n",
    "        minVal = min(nums)\n",
    "        count = [0] * (maxVal - minVal + 1)\n",
    "        for num in nums:\n",
    "            count[num - minVal] += 1\n",
    "        sum = 0\n",
    "        for i in range(0, len(count)):\n",
    "            sum += count[i]\n",
    "            count[i] = sum\n",
    "        tmp = list(nums)\n",
    "        for i in range(-1, -len(tmp) - 1, -1):\n",
    "            index = tmp[i] - minVal\n",
    "            countVal = count[index]\n",
    "            nums[countVal - 1] = tmp[i]\n",
    "            count[index] -= 1\n",
    "\n",
    "    \"\"\" \n",
    "        基数排序（稳定）\n",
    "\n",
    "        时间复杂度：O(d*(n + k))，d为最大值的位数\n",
    "        空间复杂度：O(n + k)\n",
    "     \"\"\"\n",
    "    def __method6(self, nums: List[int]):\n",
    "        # 计数排序\n",
    "        def countingSort(nums: List[int], bucket: List[int]):\n",
    "            maxVal = max(bucket)\n",
    "            minVal = min(bucket)\n",
    "            count = [0] * (maxVal - minVal + 1)\n",
    "            for num in bucket:\n",
    "                count[num - minVal] += 1\n",
    "            sum = 0\n",
    "            for i in range(0, len(count)):\n",
    "                sum += count[i]\n",
    "                count[i] = sum\n",
    "            tmp = list(bucket)\n",
    "            for i in range(-1, -len(tmp) - 1, -1):\n",
    "                index = bucket[i] - minVal\n",
    "                countVal = count[index]\n",
    "                nums[countVal - 1] = tmp[i]\n",
    "                count[index] -= 1\n",
    "\n",
    "        maxVal = max(nums)\n",
    "        bit = 1\n",
    "        while maxVal >= 10:\n",
    "            maxVal /= 10\n",
    "            bit += 1\n",
    "\n",
    "        def bucketMap(item):\n",
    "            return math.floor(item / rate) % 10\n",
    "        rate = 1\n",
    "        for i in range(0, bit):\n",
    "            bucket = list(map(bucketMap, nums))\n",
    "            countingSort(nums = nums, bucket = bucket)\n",
    "            rate *= 10\n",
    "\n",
    "    \"\"\" \n",
    "    双指针（最优方式）\n",
    "\n",
    "    可以想象将数组划分为3个区域：0区域 | 1区域 | 2区域\n",
    "    left表示0区域右边界（初始为-1），right为2区域左边界（初始为n），\n",
    "    i表示1区域末尾，初始为0，i右侧的都是未遍历到的元素；\n",
    "    遍历数组\n",
    "        如果遍历到的元素为0，0区域需要扩展1个，则将i位置元素和left右侧1位元素交换，并且left、i均右移；\n",
    "        如果遍历到的元素为1，则i右移；\n",
    "        如果遍历到的元素为2，2区域需要扩展1个，则将i位置元素和right左侧1位元素交换，并且right左移，i右移；\n",
    "    当i和right重叠时，遍历停止，此时3个区域形成；\n",
    "\n",
    "    时间复杂度：O(n)\n",
    "    空间复杂度：O(1)\n",
    "     \"\"\"\n",
    "    def __method7(self, nums: List[int]):\n",
    "        def swap(nums: List[int], a: int, b: int):\n",
    "            tmp = nums[a]\n",
    "            nums[a] = nums[b]\n",
    "            nums[b] = tmp\n",
    "        \n",
    "        n = len(nums)\n",
    "        left = -1\n",
    "        right = n\n",
    "        i = 0\n",
    "        target = 1\n",
    "        while i < right:\n",
    "            if nums[i] < target:\n",
    "                # 如果遍历到的元素为0，0区域需要扩展1个\n",
    "                swap(nums, left + 1, i)\n",
    "                left += 1\n",
    "                i += 1\n",
    "            elif nums[i] == target:\n",
    "                i += 1\n",
    "            else:\n",
    "                # 如果遍历到的元素为2，2区域需要扩展1个\n",
    "                swap(nums, right - 1, i)\n",
    "                right -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        low = 0\n",
    "        high = len(nums) - 1\n",
    "        ptr = 0\n",
    "        while ptr <= high:\n",
    "            if nums[ptr] == 0:\n",
    "                nums[ptr], nums[low] = nums[low], nums[ptr]\n",
    "                low += 1\n",
    "                ptr += 1\n",
    "            elif nums[ptr] == 2:\n",
    "                nums[ptr], nums[high] = nums[high], nums[ptr]\n",
    "                high -= 1\n",
    "            else:\n",
    "                ptr += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        # i, j, k = 0, 0, 0\n",
    "        # for n in nums:\n",
    "        #     if n == 0:\n",
    "        #         nums[k] = 2\n",
    "        #         nums[j] = 1\n",
    "        #         nums[i] = 0\n",
    "        #         i += 1\n",
    "        #         j += 1\n",
    "        #         k += 1\n",
    "        #     elif n == 1:\n",
    "        #         nums[k] = 2\n",
    "        #         nums[j] = 1\n",
    "        #         j += 1\n",
    "        #         k += 1\n",
    "        #     else:\n",
    "        #         nums[k] = 2\n",
    "        #         k += 1\n",
    "        left = 0\n",
    "        for right in range(len(nums)):\n",
    "            if nums[right] == 0:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "        for right in range(left, len(nums)):\n",
    "            if nums[right] == 1:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortColors(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] == 0:\n",
    "                nums.pop(i)\n",
    "                nums.insert(0, 0)\n",
    "                if i != 0:\n",
    "                    i -= 1\n",
    "            if nums[i] == 2:\n",
    "                nums.pop(i)\n",
    "                nums.append(2)\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if all(x == 2 for x in nums[i:]) or all(x == 0 for x in nums[:i+1]):\n",
    "                i += 1\n",
    "            "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
